package algorithm
{
	import datastructure.HTNode;
	

	/**
	 * 哈夫曼树算法
	 * @author juxuan
	 * 
	 */	
	public class Huffman
	{
		private var htNodesArray:Array;
		private var huffmanNodes:Array;
		private var huffmanTree:HTNode;
		
		public function Huffman(oriValHTNodes:Array)
		{
			this.htNodesArray = new Array();
			this.huffmanTree = new HTNode();
			this.initialize(oriValHTNodes);
		}
		
		public function getHuffmanTree():HTNode
		{
			return this.huffmanTree;
		}
		
		public function getHuffmanNodes():Array
		{
			this.huffmanNodes = new Array();
			this.initFinalHuffmanNodes(this.huffmanTree);
			return this.huffmanNodes;
		}
		
		
		/**
		 * 运行 Huffman算法
		 * 
		 */		
		public function runHuffman():void
		{
			while(this.htNodesArray.length > 1)
			{
				var n1:HTNode = this.htNodesArray.shift();
				var n2:HTNode = this.htNodesArray.shift();
				var parent:HTNode = this.combine(n1,n2);
				this.htNodesArray.push(parent);
				this.htNodesArray.sortOn("probability",Array.NUMERIC);
			}
			
			this.huffmanTree = this.htNodesArray[0] as HTNode;
			this.setAllNodesDistance(this.huffmanTree);
			trace(this.htNodesArray.length);
		}
	
		private function initialize(oriValHTNodes:Array):void
		{
			for(var i:int = 0; i < oriValHTNodes.length; i++)
			{
				this.htNodesArray.push(this.makeHTNode(oriValHTNodes[i]));
			}
			this.htNodesArray.sortOn("probability",Array.NUMERIC);
		}
		
		
		private function makeHTNode(obj:Object):HTNode
		{
			var n:HTNode = new HTNode(obj.name,obj.probability);
			return n;
		}
		
		
		private function combine(n1:HTNode,n2:HTNode):HTNode
		{
			var parent:HTNode = new HTNode();
			parent.probability = n1.probability + n2.probability;
			parent.name = parent.probability.toString();
			parent.left = n1;
			parent.right = n2;
			n1.parent = parent;
			n2.parent = parent;
			
			return parent;
		}		
		
		public function getNodeCode(node:HTNode):String
		{
			if(node == null)
				return "";
			
			var code:String = "";
			var x:HTNode = node.parent;
			var y:HTNode = node;
			while(x != null)
			{
				if(y == x.left)
				{
					code = "0" + code; 
				}
				else
				{
					code = "1" + code;
				}
				y = x;
				x = x.parent;
			
			}
			return code;
		}
		
		
		public function inorder(root:HTNode):void
		{
			if(root == null)
				return;
			inorder(root.left);
			trace(root.name + ":" + root.probability + " " + root.distance);
			inorder(root.right);
		}
		
		
		public function initFinalHuffmanNodes(root:HTNode):void
		{
			if(root == null)
				return;
			initFinalHuffmanNodes(root.left);
			if(root.left == null && root.right == null)
			{
				this.huffmanNodes.push(root);
			}
			initFinalHuffmanNodes(root.right);
		}
		
		/**
		 * 返回节点和根节点之间的距离
		 * @param node
		 * @return
		 * 
		 */		
		public function getNodeDistance(node:HTNode):int
		{
			var distance:int = 0;
			var x:HTNode = this.huffmanTree;
			var y:HTNode = node;
			while(y != x)
			{
				y = y.parent;
				++ distance;
			}
			
			return distance;
		}
		
		
		
		/**
		 * 设置所有节点的距离根节点的距离
		 * @param root
		 * 
		 */		
		public function setAllNodesDistance(root:HTNode):void
		{
			if(root == null) 
				return;
			
			root.distance = getNodeDistance(root);
			if(root == this.huffmanTree)
			{
				root.OffsetX = 0;
			}
			else
			{
				if(root == root.parent.left)
				{
					root.OffsetX = root.parent.OffsetX - 100/root.distance;
				}
				else
				{
					root.OffsetX = root.parent.OffsetX + 100/root.distance;
				}
				
			}
			setAllNodesDistance(root.left);
			setAllNodesDistance(root.right);
		}
		
		
		
		
	}
}